/* eslint-disable no-bitwise */
/* eslint-disable no-console */
/* eslint-disable no-param-reassign */
/**
 * Maintain the node i max heap nature: parent >= child
 * @param A the array
 * @param index the specific index
 */
export function MaxHeapify(A: Heap, index: number): Heap {
	const value = A.get(index)
	const leftIndex = A.left(index)
	const rightIndex = A.right(index)

	let largestIndex = index
	if (leftIndex < A.heapSize && A.get(leftIndex) > value) {
		largestIndex = leftIndex
	}
	if (rightIndex < A.heapSize && A.get(rightIndex) > A.get(largestIndex)) {
		largestIndex = rightIndex
	}

	if (largestIndex !== index) {
		A.exchange(index, largestIndex)
		MaxHeapify(A, largestIndex)
	}

	return A
}

/**
 * Build heap to match the max heap nature
 * @param A the unsorted heap
 */
export function BuildMaxHeap(A: Heap): Heap {
	const halfLength = Math.floor(A.heapSize / 2)
	for (let i = halfLength - 1; i >= 0; i -= 1) {
		MaxHeapify(A, i)
	}

	return A
}

/**
 * Sort a heap from the smallest to the largest
 * @param A the heap
 */
export function HeapSort(A: Heap): Heap {
	BuildMaxHeap(A)
	for (let i = A.length() - 1; i >= 1; i -= 1) {
		A.exchange(0, i)
		A.heapSize -= 1
		MaxHeapify(A, 0)
	}
	return A
}

export function heapMaximum(A: Heap): number {
	return A.get(0)
}

export function heapExtractMaximum(A: Heap): number {
	if (A.heapSize < 1) {
		throw new Error('heap underflow')
	}

	const max = A.get(0)
	A.heapSize -= 1
	A.data[0] = A.get(A.heapSize)
	MaxHeapify(A, 0)
	return max
}

export function heapIncreaseKey(A: Heap, i: number, key: number) {
	if (key < A.get(i)) {
		throw new Error('new key is smaller than current key')
	}
	A.data[i] = key
	while (i > 0 && A.get(A.parent(i)) < A.get(i)) {
		A.exchange(i, A.parent(i))
		i = A.parent(i)
	}
}

export function maxHeapInsert(A: Heap, key: number) {
	A.heapSize += 1
	A.data[A.heapSize - 1] = -Infinity
	heapIncreaseKey(A, A.heapSize - 1, key)
}

/**
 * A sample of a Heap class
 */
export class Heap {
	#heapSize: number = 0

	constructor(public data: number[]) {
		this.#heapSize = this.data.length
	}

	/**
	 * The length of heap
	 */
	length(): number {
		let layer = 0
		let size = this.heapSize
		while (size !== 0) {
			layer += 1
			size >>= 1
		}
		return 2 ** layer - 1
	}

	/**
	 * Get the length of data
	 */
	get heapSize(): number {
		return this.#heapSize
	}

	/**
	 * Set the length of data
	 */
	set heapSize(value: number) {
		this.#heapSize = value
	}

	/**
	 * Get the value of the index
	 * @param index the value index
	 * @returns the value of the index
	 */
	get(index: number): number {
		return this.data[index]
	}

	/**
	 * Get the layer - position of an index
	 * @param index the data index
	 */
	// eslint-disable-next-line class-methods-use-this
	getPosition(index: number): {
		layer: number,
		cell: number
	} {
		let layer = 0
		let cell = 0
		let index2 = index + 1
		while (index2 !== 1) {
			cell += ((index2 & 1) << (layer))
			layer += 1
			index2 >>= 1
		}

		return { layer, cell }
	}

	/**
	 * Get the parent index of the node index
	 * @param index the node index
	 * @returns the parent index of the node index
	 */
	parent(index: number): number {
		const { layer, cell } = this.getPosition(index)

		const parentIndex = 2 ** (layer - 1) + Math.floor(cell / 2)
		return parentIndex
	}

	/**
	 * Get the left child index of the node index
	 * @param index the node index
	 * @returns the left child index of the node index
	 */
	left(index: number): number {
		const { layer, cell } = this.getPosition(index)

		const leftIndex = 2 ** (layer + 1) + cell * 2 - 1
		return leftIndex
	}

	/**
	 * Get the right child index of the node index
	 * @param index the node index
	 * @returns the right child index of the node index
	 */
	right(index: number): number {
		return this.left(index) + 1
	}

	/**
	 * Exchange vales of these 2 positions
	 * @param index1 the first index
	 * @param index2 the second index
	 */
	exchange(index1: number, index2: number): void {
		const value = this.data[index1]
		this.data[index1] = this.data[index2]
		this.data[index2] = value
	}
}
